package drds.plus.sql_process.optimizer.chooser.join;

import drds.tools.Constants;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//@Slf4j
public final class PermutationGenerator {
    private List list;
    private int listSize;
    private Stack<List> listStack = new Stack<List>();
    private Stack<Integer> indexStack = new Stack<Integer>();
    //
    private List permutation = new ArrayList();

    public PermutationGenerator(List list) {
        this.list = list;
        this.listSize = list.size();
        this.init();
    }

    public void init() {
        listStack.clear();
        listStack.push(new ArrayList(this.list));
        indexStack.push(-1);
    }

    public boolean hasNext() {
        if (this.permutation.size() != this.listSize) {//不构成一个完整的排列
            return true;
        }
        for (int i = 0; i < this.listSize; i++) {
            if (!list.get(i).equals(this.permutation.get(this.permutation.size() - 1 - i))) {
                return true;
            }
        }
        return false;//完全逆序
    }

    public List next() {
        if (Constants.developMode) {
            System.out.println("========================================================================================================================");
        }
        boolean back = true;
        //3/4=1-1/4模式{!(a||b)=!a$$!b} =>!(permutation.size() < this.list.size() || back)==permutation.size()>=this.list.size() &&! back
        while (permutation.size() < this.listSize || back) {
            back = false;
            //
            List listStackTopCopy = new ArrayList(listStack.peek());
            Integer indexStackTopCopy = indexStack.peek();
            //back
            int lastIndexOfListStackTopCopy = listStackTopCopy.size() - 1;
            if (indexStackTopCopy == lastIndexOfListStackTopCopy) {
                listStack.pop();
                indexStack.pop();
                permutation.remove(permutation.size() - 1);
                back = true;
            } else {
                //next permutation element
                //如果不是回退则是下一个可排列index=-1,index++(index==0)
                //如果是回退则是当前index++x
                indexStackTopCopy++;
                permutation.add(listStackTopCopy.get(indexStackTopCopy));
                //
                listStackTopCopy.remove((int) indexStackTopCopy);
                listStack.push(listStackTopCopy);
                //
                indexStack.pop();
                indexStack.push(indexStackTopCopy);
                indexStack.push(-1);
            }
            if (Constants.developMode) {
                System.out.println("permutation" + permutation + ",listStack" + listStack + ",indexStack=" + indexStack);
            }
        }
        return new ArrayList(permutation);
    }
}
